#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {

            vector<vector<int>> v;
            int len = nums.size();
            if (len < 4) {
                return v;
            }
            if (len == 4) {
                if (nums[0] + nums[1] + nums[2] + nums[3]== target) {
                    v.push_back(get(nums[0],nums[1],nums[2], nums[3]));
                }
                return v;
            }

            sort(nums.begin(), nums.end());

            int i = 0;
            int last_i = nums[i];

            while(i<len-3) {

                int j = len-1;
                int last_j = nums[j];

                while(j>i+2) {

                    int m = i+1;
                    int n = j-1;
                    int last_m = nums[m];
                    int last_n = nums[n];

                    while(m<n) {
                        int sum = nums[i] + nums[j] + nums[m] + nums[n];
                        if (sum == target) {
                            v.push_back(get(nums[i],nums[m],nums[n],nums[j]));

                            last_m = nums[m--];
                            while(last_m == nums[m] && m<n) {
                                last_m = nums[m++];
                            }

                            last_n = nums[n--];
                            while(last_n == nums[n] && m<n) {
                                last_n = nums[n--];
                            }
                        } else if (sum > target) {
                            n--;
                        } else {
                            m++;
                        }
                    }

                    last_j = nums[j--];
                    while(last_j == nums[j] && j>i+2) {
                        last_j = nums[j--];
                    }

                }

                last_i = nums[i++];
                while(last_i == nums[i] && i<len-3) {
                    last_i = nums[i++];
                }
            }

            return v;
        }

        vector<int> get(int a, int b, int c, int d) {
            vector<int> v = {a, b, c, d};
            return v;
        }
};

int main() {

    Solution s;
//    vector<int> nums = {1, 0, -1, 0, -2, 2};
//    vector<int> nums = {-3, -1, 0, 2, 4, 5};
//
    vector<int> nums = {-1, 2, 2, -5, 0, -1, 4};
    int target = 3;
 //   vector<int> nums = {-9,4,0,-3,6,3,-3,-9,-7,1,0,-7,-8,7,1};
 //   int target = -9;

    sort(nums.begin(), nums.end());
    for (auto i : nums) {
        cout << i << "\t";
    }
    cout << "\n";

    vector<vector<int>> ret = s.fourSum(nums, target);

    for (auto v : ret) {
        for (auto i : v) {
            cout << i << "\t";
        }
        cout << "\n";
    }

}


